package com.chj.gaoji.class15;

public class Code01_RemoveBoxes {

	public static int removeBoxes(int[] boxes) {
		int N = boxes.length;
		int[][][] dp = new int[N][N][N];
		return process(boxes, 0, N - 1, 0, dp);
	}

	public static int process(int[] boxes, int i, int j, int k, int[][][] dp) {
		if (i > j) {
			return 0;
		}
		if (dp[i][j][k] != 0) {
			return dp[i][j][k];
		}
		if (i == j) {
			dp[i][j][k] = (k + 1) * (k + 1);
			return dp[i][j][k];
		}
		while (i < j && boxes[i] == boxes[i + 1]) {
			i++;
			k++;
		}
		int ans = (k + 1) * (k + 1) + process(boxes, i + 1, j, 0, dp);
		for (int m = i + 1; m <= j; m++) {
			if (boxes[i] == boxes[m]) {
				ans = Math.max(ans, process(boxes, i + 1, m - 1, 0, dp) + process(boxes, m, j, k + 1, dp));
			}
		}
		dp[i][j][k] = ans;
		return ans;
	}

	/*
	 * 补充题目：一次可以移除具有相同颜色的连续盒子，是每次只能移除一个滑窗，而不是一次移除同一种颜色所有地方 设dp[l][r][k]
	 * 起始下标l(以0开始)，结束下标r，k表示在下标r后面紧接着有k个元素值和boxes[r]相同，的最大积分和
	 * 比如[l,l+1,···,r-1,r,值同r，值同r，值同r]
	 * 这里有3个元素和boxes[r]相同，即k==3，那么dp[l][r][3]=dp[l][r-1][0]+4*4
	 * 因为有3个和[r]相同，即可以消除4个所以加上4*4 得到初始化条件dp[l][r][k]=dp[l][r-1][0]+(k+1)*(k+1)
	 * 但是有可能在boxes[l]~boxes[r-1]中也存在和boxes[r]相同值的元素，有可能获得更大的积分和
	 * 比如[l,l+1,···,i,···,r-1,r,值同r，值同r，值同r]，假设boxes[i]==boxes[r]
	 * 那么可能先移除boxes[i+1]~boxes[r-1]，这样就能使原来的dp[l][r][3]的k=3变的更大，但是r变得更小，但是积分和更大
	 * 因此就需要在boxes[l]~boxes[r-1]中找到boxes[i]==boxes[r]
	 ** 这样子先移除boxes[i+1]~boxes[r-1]，这一部分的最大积分和是dp[i+1][r-1][0]
	 * 移除之后是[l,l+1,···,i,值同i(原来是r)，值同i(原来是r+1)，值同i(原来是r+2)，值同i(原来是r+3)]
	 * 剩下这部分是dp[l][i][k+1]
	 ** 总和起来就是dp[l][r][k]=max(dp[l][r][k],dp[i+1][r-1][0]+dp[l][i][k+1])
	 * 最后的答案就是dp[0][boxes.size()-1][0]
	 */

	public static int removeBoxes02(int[] boxes) {
		int N = boxes.length;
		int[][][] dp = new int[N][N][N];

		return get_dp(boxes, 0, N - 1, 0, dp);
	}

	public static int get_dp(int[] boxes, int l, int r, int k, int[][][] dp) {
		if (l > r) {
			return 0;
		}

		// 记忆化
		if (dp[l][r][k] != 0) {
			return dp[l][r][k];
		}

		// 尽可能的缩小r可以让递归剪枝
		while (l < r && boxes[r] == boxes[r - 1]) {
			--r;
			++k;
		}

		dp[l][r][k] = get_dp(boxes, l, r - 1, 0, dp) + (k + 1) * (k + 1);
		for (int i = l; i < r; ++i) {
			if (boxes[i] == boxes[r]) {
				dp[l][r][k] = Math.max(dp[l][r][k],
						get_dp(boxes, i + 1, r - 1, 0, dp) + get_dp(boxes, l, i, k + 1, dp));
			}
		}

		return dp[l][r][k];
	}

	public static void main(String[] args) {
		int[] arr = { 1, 1, 1, 1, 1, 3, 2, 2, 2, 1, 3, 4, 3, 1, 1, 1, 1 };
		System.out.println(removeBoxes(arr));
		System.out.println(removeBoxes02(arr));
	}
}
